今天來到我們資料結構的第四講，今天要討論的是Stack跟Queue，中文我們稱作堆疊(Stack)和佇列(Queue)，這兩個資料結構最最最大的特點就是他很簡單好懂，那我們就從Stack開始吧~

Stack

Stack最大的特點就是「先進後出」，或是「後進先出」，意思就是先進去的最後才會出來，生活上我們也很常遇到，譬如像糖果罐，你先丟進去的糖果會被新糖果覆蓋在底下，最後才會吃到，最後丟進進去的糖果，你反而一打開糖果罐就可以吃到。

Stack 最主要有幾個操作，Push(把新資料丟進推疊最上層), Pop(從最上層取出新資料), Peek(看最上層的資料是甚麼，這個操作並不會取出資料)，我們可以利用LinkedList來實作在O(1)的時間就可以完成囉。

Queue

Queue 的最大賣點則是「先進先出」，或是「後進後出」，生活中就像排隊買電影票一樣，先抵達的人可以先買票，後抵達的人就要後來才能買票囉。

最主要的操作也跟Stack一樣，Push(把新資料丟進推疊最尾端), Pop(從最前面取出新資料), Peek(看最前面的資料是甚麼，這個操作並不會取出資料)。實作上一樣我們也能夠LinkedList在O(1)的時間完成以上三種操作。

LinkedList與Stack跟Queue

上面有提到說，可以用LinkedList的特性來實作Stack跟Queue，這邊我就用圖解的方式來跟大家介紹該怎麼實作。

LinkedList實作Stack

我們利用一個head指標，當我append一個新的值的時候，我們把這個Node的next指向我原本的Node，然後把head指向新的Node，這樣就完成拉！對了，這張圖我append了2次喔！

當我要Pop的時候，我們只需要刪除當前head的Node然後把head指標往前移一格這樣就完成Pop這個動作了(當然會可能需要一個temp指標不然把head的Node刪除後就會找不到head的next了)

這邊大家有沒有發現不管是Append或是Pop都只花了O(1)的時間呢？Peek更不用說拉，就直接回傳當前head的值就可以了。

LinkedList實作Queue

如果要實作Queue的話我們還會需要一個tail也就是尾巴指標來去紀錄我最尾巴的地方，這樣當我append的時候我就可以直接增加新的Node到tail後面，就不用從頭找過去，這樣時間複雜度就可以從O(n)進步到O(1)。

Pop的話跟Stack也是一樣的，我們把head指標當前的Node刪除，然後移動到下一個Node，這樣就完成拉！

結論

Stack跟Queue相對來說是比較好懂的資料結構，這邊還是要提醒大家要注重資料結構的概念而不用太拘泥於實作，因為不同語言的library實作方式可能不一樣，但是用法跟概念會是一樣的喔！